package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
https://programmercarl.com/%E5%91%A8%E6%80%BB%E7%BB%93/20201003%E4%BA%8C%E5%8F%89%E6%A0%91%E5%91%A8%E6%9C%AB%E6%80%BB%E7%BB%93.html#%E5%91%A8%E4%B8%80
https://leetcode.cn/problems/same-tree/description/

100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
 */
class leetcode_100 {
    @Test
    fun test_1() {
        val p = TreeNode(1)
        val p_2 = TreeNode(2)
        val p_3 = TreeNode(3)
        p.left = p_2
        p.right = p_3

        val q = TreeNode(1)
        val q_2 = TreeNode(2)
        val q_3 = TreeNode(3)
        q.left = q_2
        q.right = q_3

        val actual = isSameTree(p, q)
        val expect: Boolean = true
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val p = TreeNode(1)
        val p_2 = TreeNode(2)
        p.left = p_2

        val q = TreeNode(1)
        val q_2 = TreeNode(2)
        q.right = q_2

        val actual = isSameTree(p, q)
        val expect: Boolean = false
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_3() {
        val p = TreeNode(1)
        p.left = TreeNode(2)
        p.right = TreeNode(1)

        val q = TreeNode(1)
        q.left = TreeNode(1)
        q.right = TreeNode(2)

        val actual = isSameTree(p, q)
        val expect: Boolean = false
        Assert.assertEquals(expect, actual)
    }

    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
//        return isSameTree1(p, q)
        return isSameTree2(p, q)
    }

    private fun isSameTree1(p: TreeNode?, q: TreeNode?): Boolean {
        // 深度遍历 - 后序遍历 - 递归
        // T - N
        // S - N
        // 终止条件
        if (null == p && q == null) {
            return true
        }
        if (p == null && q != null) {
            return false
        }
        if (p != null && q == null) {
            return false
        }
        if (p != null && q != null && p.`val` != q.`val`) return false
        // 左
        val isSameLeft: Boolean = isSameTree1(p?.left, q?.left)
        // 右
        val isSameRight: Boolean = isSameTree1(p?.right, q?.right)

        // 中
        val isSame = isSameLeft == true && isSameRight == true
        return isSame
    }

    private fun isSameTree2(p: TreeNode?, q: TreeNode?): Boolean {
        // 广度遍历 - 迭代
        // T - N
        // S - N

        val queue: LinkedList<TreeNode?> = LinkedList<TreeNode?>()
        queue.offer(p)
        queue.offer(q)

        // 终止条件
        while (!queue.isEmpty()) {
            val left = queue.poll()
            val right = queue.poll()
            // 终止条件
            if (null == left && right == null) {
                // TODO: continue，不是break
                continue
            }
            if (left == null && right != null) {
                return false
            }
            if (left != null && right == null) {
                return false
            }
            if (left != null && right != null && left.`val` != right.`val`) return false
            queue.offer(left?.left)
            queue.offer(right?.left)
            queue.offer(left?.right)
            queue.offer(right?.right)
        }
        return true
    }

    fun isSameTree3(p: TreeNode?, q: TreeNode?): Boolean {
        /**
         * 前序遍历
         */
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if(null == p && null == q){
            return true
        }

        if(null == p && null != q){
            return false
        }

        if(null != p && null == q){
            return false
        }

        // 3 确定单层递归的处理逻辑：前序遍历
        if(null != p && null != q){
            // 中
            if(p.`val` != q.`val`){
                return false
            }
            // 左
            val isLeftSame= isSameTree(p.left, q.left)
            if(!isLeftSame){
                return false
            }

            // 右
            val isRightSame = isSameTree(p.right, q.right)
            if(!isRightSame){
                return false
            }
            return true
        }
        return false
    }
}